home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / VECTOR.H < prev   
C/C++ Source or Header  |  1992-09-29  |  15KB  |  319 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MJF 03/27/89 -- Initial design
  13. // Updated: MBN 04/18/89 -- Modification to support dynamic vectors, provide
  14. //                          mechanism to define default allocation size, and
  15. //                          separation of arithmetic vector to another class.
  16. // Updated: MBN 05/08/89 -- Parameterized the class Vector<Type>
  17. // Updated: MBN 05/26/89 -- Removed the non-destructive forms of the methods
  18. //                          and implemented the notion of current position.
  19. // Updated: MBN 06/07/89 -- Added growth ratio slot and resize method
  20. // Updated: MBN 06/20/89 -- Changed returns types from Vector<Type>& to void
  21. // Updated: LGO 07/13/89 -- Inherit from Generic
  22. // Updated: MBN 08/15/89 -- Added const qualifer to arguments where necessary
  23. // Updated: MBN 08/20/89 -- Changed usage of template to reflect new syntax
  24. // Updated: MBN 08/31/89 -- Added conditional exception handling and base class
  25. // Updated: LGO 10/02/89 -- Make destructor inline
  26. // Updated: MBN 10/10/89 -- Changed "current_position" to "curpos" 
  27. // Updated: MBN 10/19/89 -- Added optional argument to set_compare method
  28. // Updated: MBN 11/01/89 -- Added constructor with user-provided storage param
  29. // Updated: LGO 11/09/89 -- Initialize alloc_size and growth_ratio
  30. // Updated: MBN 11/13/89 -- Optimize sort for one element case
  31. // Updated: LGO 12/05/89 -- Performance enhancements to most methods
  32. // Updated: LGO 12/05/89 -- Make sort/merge predicate ANSI compatable
  33. // Updated: LGO 12/12/89 -- Make copy, fill and search take exclusive end args.
  34. // Updated: LGO 01/02/89 -- Add get and put methods
  35. // Updated: MBN 02/22/90 -- Changed size arguments from long to unsigned long
  36. // Updated: MJF 05/31/90 -- Use memcpy in resize
  37. // Updated: MJF 05/31/90 -- Use "delete [] data"
  38. // Updated: MJF 06/30/90 -- Added base class name to constructor initializer
  39. // Updated: VDN 02/21/92 -- New lite version, copy data with = of Type class
  40. // Updated: JAM 08/12/92 -- removed DOS specifics, stdized #includes
  41. // Updated: JAM 08/12/92 -- modernize template syntax, remove macro hacks
  42. // Updated: JAM 09/28/92 -- index/size/pos type changed from [u]long to size_t
  43. // 
  44. //
  45. // The Vector<Type> class is publicly derived from  the  Vector class and
  46. // implements single dimensional vectors   of a user specified type.    This is
  47. // accomplished by using    the   parameterized type capability   of C++.   The
  48. // Vector<Type>  class   is  dynamic  in the  sense  that an   object can  grow
  49. // dynamically if necessary.   The growth size is determined  by the value of a
  50. // static  allocation  size variable  for  the  class.  However,  fixed  length
  51. // vectors are also supported by setting this variable to INVALID.
  52. // 
  53. // Each vector object contains a protected data section that has a slot to hold
  54. // the current  size  of the  vector and a pointer  to an allocated block large
  55. // enough to hold "size" elements of type "Type". A  slot to hold the number of
  56. // elements is also provided. A single protected  slot contains  a pointer to a
  57. // compare  function to be  used in equality operations.  The  default function
  58. // used is the built-in == operator.  Finally, a current  position slot is used
  59. // to maintain the index of the last element affected by an operation.
  60. //
  61. // Five different constructors are  provided.  The  first constructor  takes no
  62. // arguments and creates an empty Vector object of a specified type. The second
  63. // constructor takes  a single  argument  specifying the  initial   size of the
  64. // Vector.  The third   constructor takes two  required   arguments,  the first
  65. // specifiying  the inital  size  of  the Vector  and  the  second providing an
  66. // initialization value to  assign to  each element.  The fourth constructor is
  67. // similar to  the third, except that it  takes a  variable number of arguments
  68. // after the size to allow for the initialization of any  number of elements of
  69. // the Vector to different  arbitrary values.  Finally, the  fifth  constructor
  70. // takes a single argument consisting of a reference to a Vector and duplicates
  71. // its size and element values.
  72. // 
  73. // The Vector class implements the notion of a current position. This is useful
  74. // for iterating through the  elements  of a  Vector.  The current  position is
  75. // maintained in an  integer and  is   set  or reset  by all methods  affecting
  76. // elements   in the Vector  class. Methods  to   reset,  move to the  next and
  77. // previous, find, and get the value at the current position are provided.
  78. //
  79. // Methods are provided  to  destructively   perform reverse, remove,  replace,
  80. // prepend, append, merge, sort, and insert operations on a Vector object.   In
  81. // addition, several miscelaneous methods  support  resize, copy, fill, length,
  82. // search,  push, push_new, pop,  and   position functions.  The assignment and
  83. // element accessor functions allow for individual elements of the vector to be
  84. // set and read.  Finally, both equality and non-equality tests are implemented
  85. // via  a user-defined  comparison function  as  well as  overloaded input  and
  86. // output operators.
  87. //
  88.  
  89. #ifndef VECTORH                    // If no definition for Vector
  90. #define VECTORH                    // define the vector symbol
  91.  
  92.  
  93. #ifndef BASE_VECTORH                // If no definition for base
  94. #include <cool/Base_Vector.h>            // Include the class header
  95. #endif
  96.  
  97. #include <stddef.h>                // for size_t
  98. #include <stdarg.h>                // for variable arglist
  99. #include <new.h>                // include the new header file
  100.  
  101. template <class Type>
  102. class CoolVector : public CoolBaseVector {
  103. public:
  104.   CoolVector ();                // Vector v; 
  105.   CoolVector (size_t);        // Vector v(10);
  106.   CoolVector (void*, size_t);    // Vector with static storage
  107.   CoolVector (size_t, const Type&); // Vector v(10,x);
  108.   CoolVector (size_t, size_t, Type, ...); // Vector v(10,3,x,y,z);
  109.   CoolVector (const CoolVector&);     // CoolVector v = y;
  110.   ~CoolVector ();                 // Destructor
  111.   
  112.   CoolVector& operator= (const CoolVector&); // v = vec1;
  113.   CoolVector& operator= (const Type&);         // v = 0; (set elements)
  114.   inline Type& operator[](size_t) const;         // return element
  115.   inline Type& get(size_t n);                 // Return element, set curpos
  116.   inline Boolean put(const Type& x, size_t n);         // Sets nth data-node to x
  117.   
  118.   Boolean operator== (const CoolVector&) const; // Compare 2 CoolVectors 
  119.   inline Boolean operator!= (const CoolVector&) const; // Compare 2 CoolVectors
  120.   
  121.   friend ostream& operator<< (ostream&, const CoolVector&); // output
  122.   /*inline##*/ friend ostream& operator<< (ostream&, const CoolVector*);
  123.   
  124.   inline Type& value ();            // Value at current position
  125.   inline size_t position () const;        // Return current position 
  126.   inline size_t set_length (size_t);        // Set length of CoolVector
  127.   inline void set_growth_ratio (float);        // Set growth ration
  128.   inline void set_alloc_size (size_t);        // Set allocation size
  129.   void set_compare (Boolean (*comp)(const Type&, const Type&) = NULL); // Compare function
  130.   
  131.   void resize (size_t);                // Resize vector
  132.   void fill (const Type&, size_t start, size_t end); // set elements
  133.   void fill (const Type& value, size_t start=0) // set elements thru length
  134.     { fill(value, start, length()); }
  135.  
  136.   void copy (const CoolVector&, size_t start, size_t end);
  137.   void copy (const CoolVector& value, size_t start = 0)
  138.     { copy(value, start, length()); }
  139.  
  140.   inline size_t position (const Type& , int dir = +1); // Index of 1st occurrence
  141.   Boolean find (const Type&, size_t start, int dir = +1); 
  142.   Boolean search (const CoolVector& sequence, size_t start, size_t end);
  143.   Boolean search (const CoolVector& sequence, size_t start=0)
  144.     { return search(sequence, start, length()); }
  145.  
  146.   Type& pop ();                    // Remove/return last element
  147.   Boolean push (const Type&);            // Add element to end of vector
  148.   Boolean push_new (const Type&);        // Append element if not there
  149.  
  150.   Boolean replace (const Type&, const Type&, int dir = +1);// Replace first occur
  151.   Boolean replace_all (const Type&, const Type&); // Replace all occurrences
  152.   Boolean prepend (const CoolVector&);    // Prepend vector 
  153.   Boolean append (const CoolVector&);    // Append vector
  154.   void reverse ();                // Reverse order of elements
  155.   void merge (const CoolVector&, int (*pred)(const Type&, const Type&)); // Merge
  156.   void sort (Boolean (*pred)(const Type&, const Type&));                   // Sort 
  157.   
  158.   Type remove ();                // Remove item at curpos 
  159.   Boolean remove (const Type&, int dir = +1);    // Shifts to preserve relative order
  160.   Boolean remove_duplicates ();            // O(n^2) time.
  161.   Boolean insert_before (const Type&);    // before curpos
  162.   Boolean insert_after (const Type&);    // after curpos
  163.   Boolean insert_before (const Type&, size_t index); // before index
  164.   Boolean insert_after (const Type&, size_t index);  // after index
  165.  
  166.   // shuffle current and last elmt instead of shifting elmts to preserve order
  167.   Type shuffle_remove ();            // Remove and shuffle last elmt up
  168.   Boolean shuffle_remove (const Type&, int dir = +1); // to fill hole.
  169.   Boolean shuffle_insert_before (const Type&); // before curpos
  170.   Boolean shuffle_insert_after (const Type&);  // after curpos
  171.   Boolean shuffle_insert_before (const Type&, size_t index); // before index
  172.   Boolean shuffle_insert_after (const Type&, size_t index);  // after index
  173.  
  174. protected:
  175.   Type* data;                    // Pointer to allocated storage
  176.   static Boolean (*compare_s)(const Type&, const Type&);    // Pointer operator== function
  177.   void grow (size_t min_size);            // Make the CoolVector bigger
  178.  
  179. private:
  180.   friend Boolean CoolVector_is_data_equal (const Type& t1, const Type& t2);
  181. };
  182.  
  183. // Type& value () -- Return value at current position.
  184. // Input:            None
  185. // Output:           Type reference to value at current position
  186.  
  187. template<class Type> 
  188. inline Type& CoolVector<Type>::value () {
  189. #if ERROR_CHECKING
  190.   if (this->curpos == INVALID_POS)            // If INVALID current position
  191.     this->value_error (#Type);            // Raise exception
  192. #endif
  193.   return (this->data[this->curpos]);
  194. }
  195.  
  196.  
  197. // Type& operator[] () -- Access an individual element from a vector.
  198. //                        Range checking is not performed.
  199. // Input:                 Integer index of element to access
  200. // Output:                Type reference of element
  201.  
  202. template<class Type> 
  203. inline Type& CoolVector<Type>::operator[] (size_t n) const {
  204.   return this->data[n];
  205. }
  206.  
  207.  
  208. // get() -- Returns the element of THIS.
  209. // Input:   A positive integer index.
  210. // Output:  A Type reference of data in the nth element of THIS.
  211.  
  212. template <class Type> 
  213. inline Type& CoolVector<Type>::get(size_t n) {
  214. #if ERROR_CHECKING  
  215.   if (n >= this->number_elements) // If index out of range
  216.     this->bracket_error (#Type, n);        // Raise exception
  217. #endif
  218.   this->curpos = n;                // Update current position
  219.   return this->data[n];
  220. }
  221.  
  222. // put() -- Replaces the data slot of the CoolVector element and if
  223. //          successful, returns the  new data item.
  224. // Input:   A Type reference and a positive integer index.
  225. // Output:  TRUE if nth element exists, FALSE otherwise.
  226.  
  227. template <class Type> 
  228. inline Boolean CoolVector<Type>::put(const Type& x, size_t n) {
  229.   if (n >= this->number_elements)        // False if index out of range
  230.     return FALSE;
  231.   else {
  232.     this->curpos = n;                // Update current position
  233.     this->data[n] = x;                // Store data
  234.     return TRUE;
  235.   }
  236. }
  237.  
  238.   
  239. // Boolean operator!= -- Test for inequality of the data of two vectors
  240. // Input:                Reference to CoolVector object
  241. // Output:               TRUE/FALSE
  242.  
  243. template<class Type> 
  244. inline Boolean CoolVector<Type>::operator!= (const CoolVector<Type>& v) const {
  245.   return (!operator== (v));
  246. }
  247.  
  248.  
  249. // size_t position () -- Return current position.
  250. // Input:              None
  251. // Output:             Integer representing current position
  252.  
  253. template<class Type> 
  254. inline size_t CoolVector<Type>::position () const {
  255.   return this->CoolBaseVector::position ();
  256. }
  257.  
  258.  
  259. // size_t position () -- Find first occurrence of element in a CoolVector,
  260. //                     from start or end of vector respectively if dir = +1, -1.
  261. // Input:              Element value searching for, and search direction
  262. // Output:             Integer representing index or -1 if not found
  263.  
  264. template<class Type> 
  265. inline size_t CoolVector<Type>::position (const Type& value, int dir) {
  266.   size_t start = 0;            // start from beginning
  267.   if (dir == -1) start = this->number_elements - 1; // or end of array
  268.   if (this->find(value, start, dir))        // search least or most 
  269.     return this->curpos;            // recent first
  270.   else 
  271.     return INVALID_POS();
  272. }
  273.  
  274. // size_t set_length () -- Set the number of elements in a CoolVector object.
  275. //                       If there is not enough storage allocated, set to
  276. //                       maximum size for storage.
  277. // Input:                Length value
  278. // Output:               Integer representing number of elements
  279.  
  280. template<class Type> 
  281. inline size_t CoolVector<Type>::set_length (size_t n) {
  282.   this->CoolBaseVector::set_length (n, "Type");    // Call base class with type
  283.   return this->length();            // Return length
  284. }
  285.  
  286.  
  287. // void set_alloc_size () -- Set the default allocation size growth rate.
  288. // Input:                    Growth size in number of elements
  289. // Output:                   None
  290.  
  291. template<class Type> 
  292. inline void CoolVector<Type>::set_alloc_size (size_t n) {
  293.   this->CoolBaseVector::set_alloc_size (n, "Type");    // Call base class with size
  294. }
  295.  
  296.  
  297. // void set_growth_ratio () -- Set the growth percentage for the CoolVector object
  298. // Input:                      Float ratio
  299. // Output:                     None
  300.  
  301. template<class Type> 
  302. inline void CoolVector<Type>::set_growth_ratio (float ratio) {
  303.   this->CoolBaseVector::set_growth_ratio (ratio, "Type"); // Call base class with size
  304. }
  305.  
  306. // ostream& operator<< () -- Overload the output operator for CoolVector pointer
  307. // Input:                    Ostream reference and CoolVector pointer
  308. // Output:                   Ostream reference
  309.  
  310. template<class Type>
  311. inline ostream& operator<< (ostream& os, const CoolVector<Type>* v) {
  312.   return operator<< (os, *v);
  313. }
  314.  
  315. #include <cool/Vector.C>   // required for most template implementations
  316.  
  317. #endif                        // End ifdef of VECTORH
  318.  
  319.